#include<iostream>
#include<stdlib.h>

using namespace std;

void swap(int* num1,int* num2)
{
    int temp=*num1;
    *num1=*num2;
    *num2=temp;
}

void AdjustDown(int* a,int size,int root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)//可能只有左子树
	{
		if (child + 1 < size && a[child + 1] > a[child])//若存在右子树
		{
			child++;
		}
		if (a[parent] < a[child])//再判断
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}	
}



void heap_sort(int* arr,int sz)
{
    //建大堆，升序，建堆最好使用向下调整
    int root=(sz-1-1)/2;    //第一个-1是个数和下标差1，第二个-1是可能最后一个是右子树
    while(root>=0)
    {
        AdjustDown(arr,sz,root);
        root--;
    }
    //类似删除的操作进行排序
    int end=sz-1;
    while(end)
    {
        swap(&arr[0],&arr[end]);
        AdjustDown(arr,end,0);
        end--;
    }
}


int main()
{
    int arr[10];
    srand((unsigned int)time(nullptr));
    for(int i=0;i<10;i++)
    {
        arr[i]=rand()%10;
    }
    heap_sort(arr,10);
    for(int i=0;i<10;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
    return 0;
}